package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;
import com.eatme.core.heap.MaxHeap;

import java.util.Arrays;

public class HeapSortV2 {

    private HeapSortV2() {

    }

    public static <E extends Comparable<E>> void sort(E [] data) {
        if (data.length<=1) return;
        for (int i = (data.length - 2)/2; i >=0 ; i--) {
            siftDown(data,i,data.length);
        }
        for (int i = data.length-1; i >=0; i--) {
            swap(data,0,i);
            siftDown(data,0,i);
        }
    }

    // 对data[0,n) 所形成的最大堆中,索引k的元素,执行sifiDown
    private static  <E extends Comparable<E>> void siftDown(E[] data,int k,int n) {
        while (2 * k + 1 < n) {
            int j = 2 * k + 1; //在此循环中,data[k]和data[j]交换位置
            if (j + 1 < n &&
                    data[j + 1].compareTo(data[j]) > 0)
                j++;
            // data[j] 是 leftChild 和 rightChild 中的最大值

            if (data[k].compareTo(data[j])>=0)
                break;
            swap(data,k,j);
            k=j;
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] =arr[j];
        arr[j] =t;
    }

    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("RandomArray");
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr_1 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_2 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_3 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_4 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_5 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_6 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_7 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_8 = Arrays.copyOf(arr,arr.length);
        Integer[] arr_9 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("HeapSort",arr);
        SortingHelper.sortTest("HeapSortV2",arr_9);
        SortingHelper.sortTest("MergeSort",arr_1);
        SortingHelper.sortTest("MergeSortV2",arr_2);
        SortingHelper.sortTest("MergeSortV3",arr_3);
        SortingHelper.sortTest("MergeSortV4",arr_4);
        SortingHelper.sortTest("MergeSortBU",arr_5);
        SortingHelper.sortTest("QuickSortV3",arr_6);
        SortingHelper.sortTest("QuickSortV4",arr_7);
        SortingHelper.sortTest("QuickSortV5",arr_8);


    }
}
